package com.sortDemo;

import java.util.Arrays;

/**
 * 希尔排序法
 * 对插入排序法的一个优化算法
 */
public class ShellSort {

   public static void main (String[] args) {
      // 对 arr 进行拷贝，不改变参数内容
      int[] arr = {7, 15, 3, 1, 634, 23};


      int gap = 1;
      while (gap < arr.length) {
         gap = gap * 3 + 1;
      }


      while (gap > 0) {
         for (int i = gap; i < arr.length; i++) {
            int tmp = arr[i];
            int j = i - gap;
            while (j >= 0 && arr[j] > tmp) {
               arr[j + gap] = arr[j];
               j -= gap;
            }
            arr[j + gap] = tmp;
         }
         gap = (int) Math.floor(gap / 3);
      }

      System.out.println(Arrays.toString(arr));
   }
}
